#include "SList.h"
#include <stdlib.h>
#include <assert.h>

//什么时候需要传二级指针:需要改变头部的指针phead,phead要指向其他的节点或NULL的时候

void SListPrint(SLTNode* phead)          //打印链表,phead为指向第一个元素的指针
{
	SLTNode* cur = phead;                //要遍历phead,所以创建一个cur,一直指向当前元素的指针
	while (cur != NULL)                  //循环打印每个元素
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

SLTNode* BuyListNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));   //为要添加的元素分配空间

	if (newnode == NULL)                                    //malloc,realloc 与 if NULL配套
	{
		printf("malloc failed\n");
		exit(-1);
	}

	newnode->data = x;
	newnode->next = NULL;                             //初始值为空,后面尾插是不用再写一遍
	return newnode;
}

void SListPushFront(SLTNode** pphead, SLTDateType x)           //头插  很简单
{
	SLTNode* newnode = BuyListNode(x);                         //创造新节点
	newnode->next = *pphead;                 //新节点的Next指向原来头部
	*pphead = newnode;                       //原来的头部指向现在的头结点,也就是刚创建的新节点

}

void SListPopFront(SLTNode** pphead)                           //头删     多考虑
{
	assert(*pphead != NULL);

	/*SLTNode* tmp = *pphead;
	*pphead = (*pphead)->next;
	free(tmp);
	tmp = NULL;*/

	SLTNode* tmp = (*pphead)->next;
	free(*pphead);
	*pphead = tmp;

}

void SListPushBack(SLTNode** pphead, SLTDateType x)   //尾插     
{                                     //phead是一个指向结构体的指针,尾插时phead要指向新节点,要在指针中修改,所以要用二级指针
									  //用二级指针不仅是为了防止为空,尾插第一个节点时需要
	SLTNode* newnode = BuyListNode(x);
	if (*pphead == NULL)             //链表为空,没有元素,也没有next,直接将头指针指向newnode
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;          //链表有元素,开始寻找末尾的节点,之后末尾节点的next指向newnode
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}



void SListPopBack(SLTNode** pphead)                    //尾删     又三种情况:1.零个节点  2.一个节点 3..两个及以上节点
{
	//1.若链表已空

	//if ((*pphead) == NULL     //温柔
	//{
	//	printf("链表已空,无法删除!\n");
	//	return;
	//} 

	assert(*pphead != NULL);    //粗暴

	//2.若链表内只有一个节点

	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		/*SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}

		free(tail);
		tail = NULL;

		prev->next = NULL;*/

		//另一种写法

		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}



SLTNode* SLTNFind(SLTNode* phead, SLTDateType x)                   //查找   返回值为SLTNode*
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)               //注意是cur, 不是cur -> next
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)         //定点前插入   两个参数节点 pos只带一个*   参数中含pphead
{
	SLTNode* newnode = BuyListNode(x);
	if (pos == *pphead)
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else
	{
		SLTNode* posPrev = *pphead;
		while (posPrev->next != pos)
		{
			posPrev = posPrev->next;
		}
		posPrev->next = newnode;
		newnode->next = pos;
	}
}

void SListInsertAfter(SLTNode* pos, int x)                 //定点后插入,简单,函数只是改变pos中的next的值,而不改变pos本身,因此不用二级指针
{
	SLTNode* newnode = BuyListNode(x);
	newnode->next = (pos)->next;                           //和下面一行的顺序不能改变
	(pos)->next = newnode;

}

void SListPop(SLTNode** pphead, SLTNode* pos)          //定点删除    参数两个节点  要不要pphead,就看有没有操作pphead的情况,要不要考虑if
{
	assert(pphead);                                    //指针一定不为空,防止实参传成plist(应该是&plist)
	SLTNode* posPrev = *pphead;
	if (*pphead == pos)
	{
		*pphead = pos->next;
		free(pos);
		pos = NULL;
	}

	while (posPrev->next != pos)
	{
		posPrev = posPrev->next;
	}
	posPrev->next = pos->next;
	free(pos);
	pos = NULL;                                         //无意义,pos传递的是一级指针,不能操作实参

}

void SListPopAfter(SLTNode* pos)                        //定点后删除
{
	assert(pos);
	assert(pos->next);                                  //防止传错参数
	SLTNode* after = pos->next;
	pos -> next= after->next;
	free(after);
	after = NULL;                                       //after在函数内部,置不置空都一样

}

void SListDestory(SLTNode** pphead)                     //销毁
{
	assert(pphead);
	SLTNode* next = NULL;
	SLTNode* pos = *pphead;
	while (pos)
	{
		next = pos->next;
		free(pos);
		pos = next;
	}
	*pphead = NULL;
}